﻿// cycle_linked_list.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
static map<ListNode*, int>my_map;
static set<ListNode*>listnode_set;
class Solution {
public:
    static bool hasCycle1(ListNode* head) {
        //map去重，时间复杂度O(n), 空间复杂度O(n)
        bool is_cycle = false;
        ListNode* curr = head;
        while (curr != nullptr)
        {
            if (my_map.count(curr))
            {
                is_cycle = true;
                break;
            }
            my_map.insert({ curr, curr->val });
            curr = curr->next;
        }
        return is_cycle;
    }
    static bool hasCycle2(ListNode* head) {
        //快慢指针
        //时间复杂度O(n)，空间复杂度O(1)
        if (nullptr == head || nullptr == head->next)
            return false;

        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast)
        {
            if (nullptr == fast || nullptr == fast->next)
            {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;

    }
    static ListNode* reverseList(ListNode* head) {
        ListNode* curr = head;
        ListNode* prev = nullptr;
        while (nullptr != curr)
        {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    static ListNode* getIntersectionNode1(ListNode* headA, ListNode* headB) {
        ListNode* curr = headA;
        bool is_inter = false;
        while (nullptr != curr)
        {
            listnode_set.insert(curr);
            curr = curr->next;
        }

        curr = headB;
        while (nullptr != curr)
        {
            if (listnode_set.count(curr))
            {
                is_inter = true;
                break;
            }
            curr = curr->next;
        }

        if (is_inter) return curr;
        return NULL;
    }
    static ListNode* getIntersectionNode2(ListNode* headA, ListNode* headB) 
    {
        if (nullptr == headA || nullptr == headB) return nullptr;

        ListNode* tmpA = headA;
        ListNode* tmpB = headB;

        while (tmpA != tmpB)
        {
            tmpA = tmpA == nullptr ? headB : tmpA->next;
            tmpB = tmpB == nullptr ? headA : tmpB->next;
        }

        return tmpA;

    }
};

int main()
{
    vector<int>arr {1, 2, 3, 4, 5};
    ListNode* head = new ListNode(arr[0]);
    ListNode* curr = head;
    for (int i = 1; i < arr.size(); i++)
    {
        curr->next = new ListNode(arr[i]);
        curr = curr->next;
    }
    ListNode* head1 = new ListNode(arr[0]);
    ListNode* curr1 = head1;
    for (int i = 1; i < arr.size(); i++)
    {
        curr1->next = new ListNode(arr[i]);
        curr1 = curr1->next;
    }
    //bool result1 = Solution::hasCycle1(head);
    //bool result2 = Solution::hasCycle2(head);
    //cout << result2;

    /*ListNode* res_node = Solution::reverseList(head);
    while (nullptr != res_node)
    {
        cout << res_node->val;
        res_node = res_node->next;
    }*/
    ListNode* res_node1 = Solution::getIntersectionNode2(head, head1);
    cout << res_node1;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
